{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "db29ba85",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    },
    "tags": []
   },
   "source": [
    "\n",
    "# Grover's Algorithm\n",
    "\n",
    "This notebook demonstrates how to use the `construct_grover_model` function, which constructs a Grover search model. For more comprehensive explanation on the algorithm see [3SAT Grover notebook](https://github.com/Classiq/classiq-library/blob/main/algorithms/grover/3_sat_grover/3_sat_grover.ipynb).\n"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "2b14dbae",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 1. Defining a Specific Example\n",
    "\n",
    "Start with specifying a specific search problem: the arithmetic variables and the arithmetic predicate."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 1,
   "id": "39df5341-4cdf-4123-a5f9-113e191db36c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:40.118386Z",
     "iopub.status.busy": "2024-05-07T13:20:40.117909Z",
     "iopub.status.idle": "2024-05-07T13:20:43.311267Z",
     "shell.execute_reply": "2024-05-07T13:20:43.310596Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import RegisterUserInput\n",
    "\n",
    "definitions = [\n",
    "    (\"a\", RegisterUserInput(size=2)),\n",
    "    (\"b\", RegisterUserInput(size=2)),\n",
    "    (\"c\", RegisterUserInput(size=3)),\n",
    "]\n",
    "expression = \"(a + b + (c & 6)) % 4 | 4 & c == 4\""
   ]
  },
  {
   "cell_type": "markdown",
   "id": "86cac86c-f0b6-41a5-9eae-485c9fed0c0e",
   "metadata": {},
   "source": [
    "## 2. Constructing and Synthesizing a Grover Model\n",
    "\n",
    "We now call the `construct_grover_model` for the specific case. We pass the number of grover operator repetitions in the model (which is based on the frequency of solutions in the search space).\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 2,
   "id": "3331b0ba-1c21-4769-8825-7ccb8a0fb9a2",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:43.314425Z",
     "iopub.status.busy": "2024-05-07T13:20:43.313849Z",
     "iopub.status.idle": "2024-05-07T13:20:43.324110Z",
     "shell.execute_reply": "2024-05-07T13:20:43.323486Z"
    }
   },
   "outputs": [],
   "source": [
    "from classiq import construct_grover_model, write_qmod\n",
    "\n",
    "qmod = construct_grover_model(\n",
    "    num_reps=1, expression=expression, definitions=definitions\n",
    ")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 3,
   "id": "313452da-2e54-4fc0-b681-6c7bd8bdf6d1",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:43.326392Z",
     "iopub.status.busy": "2024-05-07T13:20:43.326212Z",
     "iopub.status.idle": "2024-05-07T13:20:43.335620Z",
     "shell.execute_reply": "2024-05-07T13:20:43.335022Z"
    }
   },
   "outputs": [],
   "source": [
    "write_qmod(qmod, \"grover\")"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "a4e6cfec-6fde-467c-bdae-4090c341f291",
   "metadata": {},
   "source": [
    "We synthesize and visualize the circuit"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 4,
   "id": "99f8c71b-1479-49c7-bb81-8eeb24f8907e",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:43.337946Z",
     "iopub.status.busy": "2024-05-07T13:20:43.337766Z",
     "iopub.status.idle": "2024-05-07T13:20:46.767233Z",
     "shell.execute_reply": "2024-05-07T13:20:46.766534Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from classiq import show, synthesize\n",
    "\n",
    "qprog = synthesize(qmod)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 5,
   "id": "13c9a04d-1084-4843-80ee-23a0ad221522",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:46.770283Z",
     "iopub.status.busy": "2024-05-07T13:20:46.769858Z",
     "iopub.status.idle": "2024-05-07T13:20:46.847838Z",
     "shell.execute_reply": "2024-05-07T13:20:46.847145Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "Opening: https://platform.classiq.io/circuit/c727208c-a6f1-4cf0-974d-fc1c279605b3?version=0.41.0.dev39%2B79c8fd0855\n"
     ]
    }
   ],
   "source": [
    "show(qprog)"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "9900e10e",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "## 3. Executing to Find the Result\n",
    "\n",
    "Lastly, we execute the resulting quantum program"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 6,
   "id": "79e9c4c7-5c29-4d4c-a01d-26a01b7805de",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:46.850756Z",
     "iopub.status.busy": "2024-05-07T13:20:46.850260Z",
     "iopub.status.idle": "2024-05-07T13:20:48.314819Z",
     "shell.execute_reply": "2024-05-07T13:20:48.314186Z"
    },
    "pycharm": {
     "name": "#%%\n"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "from classiq import execute, set_quantum_program_execution_preferences\n",
    "from classiq.execution import (\n",
    "    ClassiqBackendPreferences,\n",
    "    ClassiqSimulatorBackendNames,\n",
    "    ExecutionPreferences,\n",
    ")\n",
    "\n",
    "backend_preferences = ExecutionPreferences(\n",
    "    backend_preferences=ClassiqBackendPreferences(\n",
    "        backend_name=ClassiqSimulatorBackendNames.SIMULATOR\n",
    "    )\n",
    ")\n",
    "\n",
    "qprog = set_quantum_program_execution_preferences(qprog, backend_preferences)\n",
    "optimization_result = execute(qprog).result()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 7,
   "id": "f037bbf6-1386-4141-8221-4496d47caf0a",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:48.319386Z",
     "iopub.status.busy": "2024-05-07T13:20:48.318311Z",
     "iopub.status.idle": "2024-05-07T13:20:48.322766Z",
     "shell.execute_reply": "2024-05-07T13:20:48.322202Z"
    },
    "tags": []
   },
   "outputs": [],
   "source": [
    "res = optimization_result[0].value"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "478e4440",
   "metadata": {
    "pycharm": {
     "name": "#%% md\n"
    }
   },
   "source": [
    "We can define a classical predicate to verify the result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 8,
   "id": "f070729b-784e-4864-89f1-9998ef43c1fc",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:48.326772Z",
     "iopub.status.busy": "2024-05-07T13:20:48.325766Z",
     "iopub.status.idle": "2024-05-07T13:20:48.330337Z",
     "shell.execute_reply": "2024-05-07T13:20:48.329748Z"
    }
   },
   "outputs": [],
   "source": [
    "def classical_predicate(a, b, c):\n",
    "    return (a + b + (c & 6)) % 4 | 4 & c == 4"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "f4b95d21-94f5-414d-a904-a8abb677faac",
   "metadata": {},
   "source": [
    "We can take the three-most probable results (the `parsed_counts` variable of the results is ordered according to the probability of the corresponding state)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 9,
   "id": "6118661f-621d-41bd-a523-c248b0a2ad4c",
   "metadata": {
    "execution": {
     "iopub.execute_input": "2024-05-07T13:20:48.334330Z",
     "iopub.status.busy": "2024-05-07T13:20:48.333324Z",
     "iopub.status.idle": "2024-05-07T13:20:48.357387Z",
     "shell.execute_reply": "2024-05-07T13:20:48.356803Z"
    }
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "a = 1 , b = 3 , c = 5 : True\n",
      "a = 2 , b = 0 , c = 7 : True\n",
      "a = 0 , b = 0 , c = 5 : True\n"
     ]
    }
   ],
   "source": [
    "NUM_SOLUTIONS = 3\n",
    "\n",
    "for k in range(NUM_SOLUTIONS):\n",
    "    parsed_res = res.parsed_counts[k].state\n",
    "    a, b, c = int(parsed_res[\"a\"]), int(parsed_res[\"b\"]), int(parsed_res[\"c\"])\n",
    "    print(\"a =\", a, \", b =\", b, \", c =\", c, \":\", classical_predicate(a, b, c))"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.11.9"
  },
  "vscode": {
   "interpreter": {
    "hash": "a07aacdcc8a415e7643a2bc993226848ff70704ebef014f87460de9126b773d0"
   }
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
